import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/31 16:02
 * @description 二分查找，对于矩阵中的某个数，不大于mid和大于mid的可以分为两个板块，从左下角开始走，<= mid 就往右走一格
 * > mid 就往上走一格，可以统计当前列不大于mid的数的数量
 */
public class Solution4 {
    public static void main(String[] args) {

    }
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // 二分左右边界
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                // 如果<=mid的数的数量 > k， 最终答案 <= mid
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            // 从左下角开始走，<= mid，那么看这一行的下一个值是否满足，同时统计满足条件的数
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
}
